package binary_tree.leetcode;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
 * @Author Stark
 * @Date 2022/3/1 20:02
 */
public class NowCoder_BSTToDList {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        //递归得到最左的结点,此时leftHead保存的就是链表的头结点
        TreeNode leftHead = Convert(pRootOfTree.left);
        //用leftTail进行遍历得到已连接的链表的尾结点
        TreeNode leftTail = leftHead;
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        //进行判空
        if(leftTail != null) {
            //将根节点和链表进行连接
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        //递归右子树
        TreeNode rightHead = Convert(pRootOfTree.right);
        if(rightHead != null){
            //再将右结点和根结点进行连接
            rightHead.left = pRootOfTree;
            pRootOfTree.right = rightHead;
        }
        return leftHead == null ? pRootOfTree : leftHead;
    }
}
